package jzOffer;

public class Num22 {
    //双指针，将快指针指在第k+1个节点，慢指针指在第1个节点，两个指针刚好间隔k个节点，所以当快指针走到空时，慢指针刚好指在倒数第k个节点
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head==null) return null;
        ListNode slow=head;
        ListNode fast=head;
        for(int i=0;i<k;i++){
            fast=fast.next;
            if(fast==null) return head;
        }
        while(fast!=null){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }
    //顺序查找，遍历两次
//    public ListNode getKthFromEnd(ListNode head, int k) {
//        if(head==null) return null;
//        int len=0;
//        ListNode node=head;
//        for(;node!=null;node=node.next){
//            len++;
//        }
//        int count=len-k;
//        for(int i=0;i<count;i++){
//            head=head.next;
//        }
//        return head;
//    }


}
